<?php
/**
 * @title 264. 丑数 II - 最小堆
 * @author start2004
 */

class iMinHeap extends SplMinHeap{
    public function compare($arr1, $arr2)
    {
        if($arr1[2] == $arr2[2]){
            return 0;
        } elseif($arr1[2] < $arr2[2]) {
            return 1;
        } else {
            return -1;
        }
    }
}

class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    function nthUglyNumber($n) {
        /**
         * @since 2020-07-30 最小堆
         */
        $heap = new iMinHeap();
        $heap->insert([1, 1, 1]);

        /**
         * @since 2020-07-30 穷列
         */
        $hashs = [
            "1" => 1,
        ];
        while($n>0){
            /**
             * @since 2020-07-30 移除最小值
             */
            list($x, $times, $min) = $heap->extract();
            // echo "n={$n}, min={$min}", PHP_EOL;

            /**
             * @since 2020-07-30 加入新的元素, 防止重复
             */
            if($times <= 3){
                if($times == 1){
                    $times = 2;
                } elseif($times == 2){
                    $times = 3;
                } else {
                    $times = 5;
                }
                $nextMin = $x*$times;

                if(!isset($hashs[$nextMin])){
                    $heap->insert([$x, $times, $nextMin]);
                    $hashs[$nextMin] = 1;
                } else {}
            } else {}

            /**
             * @since 2020-07-30 新的基数
             */
            foreach ([2,3,5] as $times){
                $newMin = $min*$times;
                if(!isset($hashs[$newMin])) {
                    $heap->insert([$min, $times, $newMin]);
                    $hashs[$newMin] = 1;
                    break;
                } else {}
            }


            $n--;
        }

        /**
         * @return
         */
        return $min;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.30_3.php
 */
$datas = [
    10,
    1690,
    5500,
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof(false);
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->nthUglyNumber($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
